/*================================================================
 *  pac.c
 *               Packing with a primitive LZW algorithm
 *
 *================================================================
 *
 * 25thanni, a demo dedicated to the 25th anniversary of the ZX81.
 *
 * (c)2006 Bodo Wenzel
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of
 * the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free
 * Software Foundation Inc., 59 Temple Place, Suite 330, Boston,
 * MA 02111-1307 USA
 *================================================================
 */

/* Externals ================================================== */

#include <stdlib.h>

#include "pack.h"

/* Constants ================================================== */

#define COUNT_BITS    4 /* tune this... */
#define BITS_PER_BYTE 8
#define MIN_COUNT     (sizeof(ENTRY) + 1)
#define OFFSET_BITS   (sizeof(ENTRY) * BITS_PER_BYTE - COUNT_BITS)
#define COUNT_MAX     ((1 << COUNT_BITS) - 1 + MIN_COUNT)
#define OFFSET_MAX    ((1 << OFFSET_BITS) - 1 + MIN_COUNT)

/* Typedefs =================================================== */

typedef unsigned short ENTRY;

typedef struct {
  unsigned char *unpacked_ptr;
  unsigned int  next;
  int           byte;
} OFFSET_LOOKUP;

/* Functions ================================================== */

size_t pac(size_t packed_len_max, unsigned char *packed,
	   size_t unpacked_len, unsigned char *unpacked) {
  unsigned int  lookup_index_first[1 << BITS_PER_BYTE];
  unsigned int  lookup_index_last[1 << BITS_PER_BYTE];
  OFFSET_LOOKUP offset_lookup[OFFSET_MAX];
  unsigned int  index, offset, entry_flags;
  unsigned char *packed_ptr, *entry_ptr;
  unsigned char *unpacked_ptr, *unpacked_max;

  /* prepare tables */
  for (index = 0; index < (1 << BITS_PER_BYTE); index++) {
    lookup_index_first[index] = OFFSET_MAX;
  }
  for (offset = 0; offset < OFFSET_MAX; offset++) {
    offset_lookup[offset].byte = -1;
  }

  unpacked_ptr = unpacked;
  unpacked_max = unpacked + unpacked_len;
  offset = 0;
  entry_flags = 1;
  packed_ptr = packed;
  entry_ptr = packed_ptr++;

  while (unpacked_ptr < unpacked_max) {
    unsigned int best_count, entry_offset;
    int          byte;

    best_count = MIN_COUNT - 1;

    /* look for a chunk */
    byte = *unpacked_ptr;
    for (index = lookup_index_first[byte];
	 index < OFFSET_MAX;
	 index = offset_lookup[index].next) {
      unsigned char *offset_try_ptr, *unpacked_try_ptr;
      unsigned int  ptr_diff;

      offset_try_ptr = offset_lookup[index].unpacked_ptr;
      unpacked_try_ptr = unpacked_ptr;
      ptr_diff = unpacked_try_ptr - offset_try_ptr;
      if (ptr_diff <= best_count) {
	break;
      }
      offset_try_ptr++;
      unpacked_try_ptr++;
      if (unpacked_try_ptr <= unpacked_max) {
	unsigned int try_count, max_count;

	try_count = 0;
	max_count = ptr_diff;
	if (max_count > COUNT_MAX) {
	  max_count = COUNT_MAX;
	}
	do {
	  try_count++;
	  if (unpacked_try_ptr >= unpacked_max
	      || try_count >= max_count) {
	    break;
	  }
	} while (*offset_try_ptr++ == *unpacked_try_ptr++);
	if (try_count > best_count) {
	  /* looks like a good candidate */
	  entry_offset = ptr_diff;
	  best_count = try_count;
	  if (best_count == COUNT_MAX) {
	    break;
	  }
        }
      }
    }

    /* add an entry */
    entry_flags <<= 1;
    if (best_count >= MIN_COUNT) {
      ENTRY        entry;
      unsigned int entry_byte;

      entry_flags |= 0x01;
      entry = (best_count - MIN_COUNT) << OFFSET_BITS;
      entry |= entry_offset - MIN_COUNT;
      for (entry_byte = 0;
	   entry_byte < sizeof(ENTRY);
	   entry_byte++) {
	*packed_ptr++ = (unsigned char)entry;
	entry >>= BITS_PER_BYTE;
      }
    } else {
      *packed_ptr++ = *unpacked_ptr;
      best_count = 1;
    }

    /* update tables */
    while (best_count-- != 0) {
      int next_byte;

      byte = *unpacked_ptr;
      if (lookup_index_first[byte] < OFFSET_MAX) {
	offset_lookup[lookup_index_last[byte]].next = offset;
      } else {
	lookup_index_first[byte] = offset;
      }
      lookup_index_last[byte] = offset;
      next_byte = offset_lookup[offset].byte;
      if (next_byte >= 0) {
	lookup_index_first[next_byte] =
	  offset_lookup[lookup_index_first[next_byte]].next;
      }
      offset_lookup[offset].byte = byte;
      offset_lookup[offset].unpacked_ptr = unpacked_ptr++;
      offset_lookup[offset].next = OFFSET_MAX;
      offset = (offset + 1) % OFFSET_MAX;
    }

    /* if the entry header is full, store it */
    if (entry_flags >= (1 << BITS_PER_BYTE)) {
      *entry_ptr = (unsigned char)entry_flags;
      entry_ptr = packed_ptr++;
      entry_flags = 1;
    }

    /* check for buffer overrun */
    if (packed_ptr > packed + packed_len_max - sizeof(ENTRY)) {
      return 0;
    }
  }

  /* if necessary, store last entry header */
  if (entry_flags != 1) {
    while (entry_flags < (1 << BITS_PER_BYTE)) {
      entry_flags <<= 1;
    }
    *entry_ptr = (unsigned char)entry_flags;
  } else {
    packed_ptr--;
  }

  return packed_ptr - packed;
}

/* The end ==================================================== */
